/*
 * @lc app=leetcode.cn id=416 lang=javascript
 *
 * [416] 分割等和子集
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  // - 状态：dp[i][j] 表示从数组的 [0,i] 下标范围内选取若干个正整数（可以是 0 个），是否存在一种选取方案使得被选取的正整数的和等于 j
  // - 初始状态：dp[0][0]=false
  // - 状态转移：dp[i][j]
  //      1. j>= nums[i]: dp[i-1][j] || dp[i-1][j-nums]
  //      2. j < nums[i]: dp[i-1][j]
  // - 答案：dp[nums.length - 1][sum/2]
  const sum = nums.reduce((a, b) => a + b, 0);
  const n = nums.length;

  if (sum % 2 !== 0) {
    return false;
  }
  if (n < 2) {
    return false;
  }

  const targetSum = sum / 2;

  const dp = new Array(n).fill(0).map((_) => new Array(targetSum).fill(false));
  dp[0][nums[0]] = true;
  for (let i = 1; i < n; i++) {
    const num = nums[i];
    for (let j = 1; j <= targetSum; j++) {
      if (j >= num) {
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[n - 1][targetSum];
};
// @lc code=end
